package leetcodecompetition.D365;

import java.util.Arrays;

/**
 * @Author: Siantar
 * @Date: 2023-10-01-10:48
 * @Description: 1.0
 */
public class T100076 {
    public int minSizeSubarray(int[] nums, int target) {
        int n = nums.length;
        long[] leftSum = new long[n];
        long[] rightSum = new long[n];
        leftSum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            leftSum[i] = leftSum[i - 1] + nums[i];
        }
        rightSum[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightSum[i] = rightSum[i + 1] + nums[i];
        }
        long sum = leftSum[n - 1];
        int t = 0;
        int res = Integer.MAX_VALUE;
        if (target / sum >= 2) {
            t = (int) (target / sum - 1);
            target = (int) (target % sum + sum);
        }
        if (target == sum) {
            res = Math.min(res, t * n + 1);
        }
        System.out.println(Arrays.toString(leftSum));
        System.out.println(Arrays.toString(rightSum));
        System.out.println(t);
        System.out.println(target);
        if (t==0&&target<sum){
            for (int i = 0; i < n; i++) {
                int j = leftFind(target - rightSum[i], leftSum);
                if (j != -1) {
                    System.out.println(i+"  "+j);
                    res = Math.min(res, n  - i + j);
                }
            }
            for (int i = 0; i < n; i++) {
                int j = leftFind(target +sum- rightSum[i], leftSum);
                if (j != -1) {
                    System.out.println(i+"  "+j);
                    res = Math.min(res, n  - i + j-n);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            int j = leftFind(target - rightSum[i], leftSum);
            if (j != -1) {
                System.out.println(i+"  "+j);
                res = Math.min(res, n  - i + j + t * n);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public int leftFind(long p, long[] ps) {
        if (p == 0) return 0;
        int l = 0, r = ps.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (ps[mid] > p) {
                r = mid - 1;
            } else if (ps[mid] < p) {
                l = mid + 1;
            } else {
                return mid + 1;
            }
        }
        return -1;
    }
}
